87. Robot
The infinite in
both directions stripe with width 1 is divided into blocks of size 1 * 1. In
one of these blocks the robot is located. It can move from one cell to another
(the robot at the figure is marked with square). Its movements are determined
by the program, each instruction is given by one of three capital letters: L, R,
S. The instruction L says the robot to move one cell to the left, the
instruction R – to move one square right, and S – to stay in the same
cell. Program execution means the sequential execution of all instruction in
it.
Write a program
that will determine how many different cells visits the robot.
Input. The program for the robot is a string of
characters L, R, S. The program consists of no more than 104 instructions.
Output. Print the number of different cells that
visits the robot performing the program.
|
Sample
input |
Sample
output |
|
RRSRRLRR |
6 |
SOLUTION
strings
Algorithm
analysis
Let the robot
initially be in the cell with number 0. Simulate its movements, memoizing the numbers of
the leftmost l and rightmost r cells where it could get. Then the
number of different cells that the robot will visit while executing its program
will be r – l + 1.
Algorithm realization
Store the input
string, the program for the robot, in the array s.
char s[10001];
Read the input
line.
gets(s);
Initially assume that robot is located at the point
with abscissa x = 0. That is, at the
start, it visited only the cells in the interval [l; r] = [0; 0].
l = x = r = 0;
Start the process of simulating the robot program. When moving to the right, increase the
value of x by 1, when moving to the left, decrease x by 1.
for(i = 0; i < strlen(s); i++)
{
if (s[i] == 'R')
x++;
if (s[i] == 'L')
x--;
After changing the value of x, recompute l and r.
if (x > r) r = x;
if (x < l) l = x;
}
Print the number of
different cells visited by robot.
printf("%d\n",r -
l + 1);
Algorithm realization –
string
Read the input
line.
cin >> s;
Initially assume that robot is located at the point
with abscissa x = 0. That is, at the
start, it visited only the cells in the interval [l; r] = [0; 0].
l = x = r = 0;
Start the process of simulating the robot program. When moving to the right, increase the
value of x by 1, when moving to the left, decrease x by 1.
for (i = 0; i <
s.size(); i++)
{
if (s[i] == 'R') x++;
if (s[i] == 'L') x--;
After changing the value of x, recompute l and r.
if (x > r) r = x;
if (x < l) l = x;
}
Print the number of
different cells visited by robot.
cout << r - l + 1 << endl;
Algorithm realization
– dynamic array
#include <stdio.h>
#include <string.h>
int l, r, x, i;
char *s;
int main(void)
{
l = x = r = 0;
s = new char[10001];
gets(s);
for(i = 0; i < strlen(s); i++)
{
if (s[i] == 'R')
x++;
if (s[i] == 'L')
x--;
if (x > r) r = x;
if (x < l) l = x;
}
printf("%d\n",r - l + 1);
delete[] s;
return 0;
}
Java
realization
import
java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
String s = con.nextLine();
int l, x, r;
l = x = r = 0;
for(int i = 0; i < s.length(); i++)
{
if (s.charAt(i) == 'R') x++;
if (s.charAt(i) == 'L') x--;
if (x > r) r = x;
if (x < l) l = x;
}
System.out.println(r-l+1);
con.close();
}
}
Python
realization
Read the input
line.
s = input()
Initially assume that robot is located at the point
with abscissa x = 0. That is, at the
start, it visited only the cells in the interval [l; r] = [0; 0].
r = l = x = 0
Start the process of simulating the robot program. When moving to the right, increase the
value of x by 1, when moving to the left, decrease x by 1.
for ch in s:
if ch == 'L': x += 1
if ch == 'R': x -= 1
After changing the value of x, recompute l and r.
r = max(r, x)
l = min(l, x)
Print the number of
different cells visited by robot.
print(r - l + 1)